<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>24. 两两交换链表中的节点</title>
  </head>
  <body>
    <script>
      //       给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

      // 示例 1：
      // 输入：head = [1,2,3,4]
      // 输出：[2,1,4,3]
      // 示例 2：

      // 输入：head = []
      // 输出：[]
      // 示例 3：

      // 输入：head = [1]
      // 输出：[1]

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/swap-nodes-in-pairs
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

      /**
       * Definition for singly-linked list.
       * */
      function ListNode(val, next) {
        this.val = val === undefined ? 0 : val
        this.next = next === undefined ? null : next
      }

      /**
       * @param {ListNode} head
       * @return {ListNode}
       */
      var swapPairs = function (head) {
        // if (!head || !head.next) {
        //   return head
        // }
        // let fri = head
        // let sec = fri.next
        // let thi = sec.next
        // head = sec // 保存链表头
        // while (true) { // 后节点交换的时候会导致节点丢失
        //   sec.next = fri
        //   fri.next = thi
        //   fri = thi
        //   if (!fri) {
        //     // 链表长度为双数
        //     break
        //   }
        //   sec = fri.next
        //   if (!sec) {
        //     // 链表长度为单数
        //     break
        //   }
        //   thi = sec.next
        // }
        // return head

        if (!head || !head.next) {
          // 当前节点为 null 或者下一节点为 null 时，不需要做交换
          return head
        }

        let fri = head // 保留当前节点
        let sec = fri.next // 保留当前节点的下一节点
        let thi = sec.next // 保留当前节点的下一节点的下一节点
        sec.next = fri // 将前面俩个节点交换
        fri.next = swapPairs(thi) // 将 thi 节点做为头节点继续递归获取该连上来的节点
        return sec
      }
    </script>
  </body>
</html>
